package sit.engreal.leetcode.problems800;

import org.junit.jupiter.api.Assertions;

import java.util.ArrayDeque;
import java.util.Map;
import java.util.TreeMap;

/**
 * <a herf="https://leetcode.cn/problems/daily-temperatures/">739. 每日温度</a>
 */
public class LeetCode739 {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        final ArrayDeque<int[]> deque = new ArrayDeque<>();
        for (int i = temperatures.length - 1; i >= 0; i--) {
            while (!deque.isEmpty() && deque.peekLast()[0] <= temperatures[i]) {
                deque.pollLast();
            }
            if (deque.isEmpty()) {
                answer[i] = 0;
            } else {
                answer[i] = deque.peekLast()[1] - i;
            }
            deque.offerLast(new int[]{temperatures[i], i});
        }
        return answer;
    }

    public static void main(String[] args) {
        final LeetCode739 demo = new LeetCode739();

        Assertions.assertArrayEquals(
                new int[]{1, 1, 4, 2, 1, 1, 0, 0},
                demo.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})
        );
    }
}
